|
A set of prototiles is aperiodic if copies of them can be assembled to create tilings, and all such tilings are non-periodic. Consequently, ''aperiodicity'' is a property of the set of prototiles; the tilings themselves are just non-periodic. Typically, distinct tilings may be obtained from a single aperiodic set of tiles.〔Actually, a set of aperiodic prototiles can always form uncountably many different tilings, even up to isometry, as proven by Nikolaï Dolbilin in his 1995 paper ''The Countability of a Tiling Family and the Periodicity of a Tiling''〕 The various Penrose tiles are the best-known examples of an aperiodic set of tiles. Today not many aperiodic sets of prototiles are known (here is a List of aperiodic sets of tiles). This is perhaps natural: the underlying undecidability of the Domino problem implies that there exists no systematic procedure for deciding whether a given set of tiles can tile the plane. A given set of tiles, in the Euclidean plane or some other geometric setting, ''admits a tiling'' if non-overlapping copies of the tiles in the set can be fitted together to cover the entire space. A given set of tiles might admit periodic tilings — that is, tilings which remain invariant after being shifted by a translation (for example, a lattice of square tiles is periodic). It is not difficult to design a set of tiles that admits non-periodic tilings as well (for example, randomly arranged tilings using a 2×2 square and 2×1 rectangle will typically be non-periodic). An aperiodic set of tiles, however, admits ''only'' non-periodic tilings. ==History== The second part of Hilbert's eighteenth problem asked for a single polyhedron tiling Euclidean 3-space, such that no tiling by it is isohedral (an anisohedral tile). The problem as stated was solved by Karl Reinhardt in 1928, but sets of aperiodic tilies have been considered as a natural extension.〔Senechal, pp 22–24.〕 The specific question of aperiodic sets of tiles first arose in 1961, when logician Hao Wang tried to determine whether the Domino Problem is decidable — that is, whether there exists an algorithm for deciding if a given finite set of prototiles admits a tiling of the plane. Wang found algorithms to enumerate the tilesets that cannot tile the plane, and the tilesets that tile it periodically; by this he showed that such a decision algorithm exists if every finite set of prototiles that admits a tiling of the plane also admits a periodic tiling. Hence, when in 1966 Robert Berger found an aperiodic set of prototiles this demonstrated that the tiling problem is in fact not decidable. (Thus Wang's procedures do not work on all tile sets, although that does not render them useless for practical purposes.) This first such set, used by Berger in his proof of undecidability, required 20,426 Wang tiles. Berger later reduced his set to 104, and Hans Läuchli subsequently found an aperiodic set requiring only 40 Wang tiles.〔Grünbaum and Shephard, section 11.1.〕 The set of 13 tiles given in the illustration on the right is an aperiodic set published by Karel Culik, II, in 1996. However, a smaller aperiodic set, of six non-Wang tiles, was discovered by Raphael M. Robinson in 1971. Roger Penrose discovered three more sets in 1973 and 1974, reducing the number of tiles needed to two, and Robert Ammann discovered several new sets in 1977. The question of whether an aperiodic set exists with only a single prototile is known as the einstein problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Aperiodic set of prototiles」の詳細全文を読む スポンサード リンク
|